package class07;

import java.util.*;

/**
 * @author zhangchaoliang
 * create 2022
 */
public class SerializeAndReconstructTree2 {

    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int data){
            value = data;
        }
    }

    public static Queue<String> preSerial(Node head){
        Queue<String> ans = new LinkedList<>();
        pres(head,ans);
        return ans;
    }

    public static void pres(Node head,Queue<String> ans){
        if (head==null){
            ans.add(null);
        }else {
            ans.add(String.valueOf(head.value));
            pres(head.left,ans);
            pres(head.right,ans);
        }
    }

    public static Queue<String> inSerial(Node head){
        Queue<String> ans = new LinkedList<>();
        ins(head,ans);
        return ans;
    }

    public static void ins(Node head,Queue<String> ans){
        if (head==null){
            ans.add(null);
        }else {
            ins(head.left,ans);
            ans.add(String.valueOf(head.value));
            ins(head.right,ans);
        }
    }

    public static Queue<String> posSerial(Node head){
        Queue<String> ans = new LinkedList<>();
        poss(head,ans);
        return ans;
    }

    public static void poss(Node head,Queue<String> ans){
        if (head==null){
            ans.add(null);
        }else {
            poss(head.left,ans);
            poss(head.right,ans);
            ans.add(String.valueOf(head.value));
        }
    }

    public static Node buildByPreQueue(Queue<String> prelist){
        if (prelist==null||prelist.size()==0){
            return null;
        }
        return preb(prelist);
    }

    public static Node preb(Queue<String> prelist){
        String value = prelist.poll();
        if (value==null){
            return null;
        }
        Node head = new Node(Integer.valueOf(value));
        head.left = preb(prelist);
        head.right = preb(prelist);
        return head;
    }

    public static Node buildByPosQueue(Queue<String> poslist){
        if (poslist==null||poslist.size()==0){
            return null;
        }
        Stack<String> stack = new Stack<>();
        while (!poslist.isEmpty()){
            stack.push(poslist.poll());
        }
        return posb(stack);
    }

    public static Node posb(Stack<String> posstack){
        String value = posstack.pop();
        if (value==null){
            return null;
        }
        Node head = new Node(Integer.valueOf(value));
        head.right = posb(posstack);
        head.left = posb(posstack);
        return head;
    }
}
